A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems

摘要

General multi-objective optimization problems are often solved by a sequenceof parametric single objective problems, so-called scalarizations. If the setof nondominated points is finite, and if an appropriate scalarization isemployed, the entire nondominated set can be generated in this way. In thebicriteria case it is well known that this can be realized by an adaptiveapproach which, given an appropriate initial search space, requires thesolution of a number of subproblems which is at most two times the number ofnondominated points. For higher dimensional problems, no linear methods wereknown up to now. We present a new procedure for finding the entire nondominatedset of tricriteria optimization problems for which the number of scalarizedsubproblems to be solved is at most three times the number of nondominatedpoints of the underlying problem. The approach includes an iterative update ofthe search space that, given a (sub-)set of nondominated points, describes thearea in which additional nondominated points may be located. In particular, weshow that the number of boxes, into which the search space is decomposed,depends linearly on the number of nondominated points.